package ink.lovejinhu.acwing.dp;

/**
 * @Author: jin
 * @ClassName: Person
 * @Date: 2021/8/24 9:00
 * @Version: V1.0
 * @Slogan: Great people are not born great, but show their greatness in the process of growing up
 **/

import java.util.Scanner;

/**
 * 01背包
 * 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
 * <p>
 * 第 i 件物品的体积是 vi，价值是 wi。
 */
public class Package01 {
    /**
     * v[]代表第i件物品的体积
     * w[]代表第i件物品的价值
     * <p>
     * 定义：只考虑前i个物品的选法，且体积不超过j
     * f(i)(j)=  Max(  f(i-1)(j),   f(i)(j-v[i])+w[i) )
     *
     * @param v
     * @param w
     * @param capcity
     * @param n
     * @return
     */
    public int gteMaxValue(int v[], int w[], int capcity, int n) {
        int[][] ints = new int[n + 1][capcity + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= capcity; j++) {
                ints[i][j] = ints[i - 1][j];   //肯定可以不选
                if (j >= v[i]) {
                    ints[i][j] = Math.max(ints[i - 1][j], ints[i][j - v[i]] + w[i]);
                }
            }
        }
        return ints[v.length - 1][capcity];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] s1 = s.split(" ");
    }

}
